package top.likeqc.leetcode.editor.cn;

/** 链接: https://leetcode.cn/problems/reach-a-number */
public class ReachANumber {
    public static void main(String[] args) {
        Solution solution = new ReachANumber().new Solution();
    }
    // leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int reachNumber(int target) {
            int t = Math.abs(target);
            int sum = 0, s = 0;
            s = (int) Math.sqrt(2 * target);
            sum = s * (s + 1) / 2;
            while (sum < t) {
                s++;
                sum += s;
            }
            int dt = sum - t;
            if (dt % 2 == 0) {
                return s;
            }
            // 若 dt 为奇数，那么还需要继续往前走，使得 dt = sum - t 为偶数
            if (s % 2 == 0) {
                // s 为偶数时， s + 1 则为奇数，奇 + 奇 = 偶
                return s + 1;
            } else {
                // s 为奇数时， s + 1 则为偶数，奇 + 偶 + 奇 = 偶
                return s + 2;
            }
        }
    }
    // leetcode submit region end(Prohibit modification and deletion)

}
